Generally, there are many opportunities for people to communicate with each other through different means of communication. For instance, a single person might be able to communicate with other people using a cellular phone, email, instant messaging, or other communication devices. In order to communicate with people, many users store contact information for their contacts. However, with the various different devices, the contact information generally is stored in a distributed environment, where each communication device may store contact information only for portion of all the person's contacts. The distributed storage of contact information makes communication difficult because the person may not have the correct contact information in the communication device the person is currently using. Further problems can complicate the issue. For example, when a communication device fails or can no longer retrieve the contact information it once stored, the person may not be able to make the communication.